Y gracias a los organizadores por invitarme.
hablar aquí.
Me siento honrado y conmovido de hablar entre mis
comunidad y hablar junto a personas cuyas obras
He estado siguiendo desde el principio de mi
trayectoria académica.
Así que, sinceramente, muchas gracias.
Así que hoy quería hablar sobre algunos
trabajo que he estado haciendo sobre la preservación de la distancia
aprendizaje automático de gráficos.
Y antes de empezar, permítanme simplemente dar
te daré una imagen que de alguna manera te motivará.
el trabajo que estábamos haciendo aquí.
Entonces, la idea que estábamos explorando es
que los gráficos tienen topología estructural en todas las escalas.
Así que puedes pensar al nivel más simple,
a escala local, tienes cosas como
invariancia local, pocos vecindarios de saltos, incluso muy pequeños
cosas como escalares por nodo, como el grado
de cada nodo.
Y estas invariantes fundamentales impulsan cosas como
consenso descentralizado.
Impulsan cosas como las redes neuronales convolucionales de paso de mensajes.
redes mediante la realización de estas agregaciones locales sucesivas.
Luego, si vas al otro extremo
del espectro, tienes la escala global.
Y puedes pensar, cuando digo
escala global aquí, estoy pensando en, tengo
dos nodos en mi gráfico.
No necesariamente están relacionados.
¿Cómo se relacionan a lo largo del gráfico?
Entonces, por ejemplo, ¿cuántos caminos hay?
¿Entre ellos?
O quizás más importante, ¿cuál es el más corto?
camino que puedo tomar para llegar desde
¿De un nodo a otro nodo?
Y este es un problema importante que impulsa
cosas como recuperación, enrutamiento, navegación, que son muy
problemas importantes en áreas como la robótica y las operaciones
investigación.
Y luego, en algún punto intermedio, tienes
la escala mesoscópica, que es algo así como
esta escala intermedia entre lo local y lo global.
Y esta escala suele revelarse en las cosas
como caminatas de varios saltos, resistencia efectiva, como Antonio
Ortega lo dijo en la primera sesión plenaria.
Y esto revelará motivos, cosas como comunidades,
cuellos de botella, y así sucesivamente.
Entonces, la forma en que pienso en esto es,
Si sé que dos nodos están conectados
por un borde, están como en
esta escala local en conjunto.
Si no están conectados por una arista, si
Me pregunto, de acuerdo, ¿están en el?
¿La misma comunidad?
Es algo así como la escala mesoscópica.
Imagina que no pertenecen a la misma comunidad.
¿A qué distancia están?
Y esto es lo que pienso como
a escala global.
Así que esta es solo una taxonomía para lo que
Me refiero a cuando me refiero a estos diferentes
balanza.
Y luego la pregunta que nos interesaba
con mi estudiante de doctorado, Milet, por la
De alguna manera, debería haber dicho, esto está en
colaboración con Shovik Dara de Georgia Tech y
Meher Chaitanya de KTH.
Entonces, lo que nos interesaba entender era:
¿Pueden los métodos de aprendizaje automático de procesamiento de señales gráficas existentes
¿Es posible integrar esta topología en todas las escalas?
Entonces, cuando se trata de incrustaciones locales, GNN,
Procesamiento de señales, lo hacen de maravilla.
Esto lo maneja magníficamente el gráfico SP y
NML, al menos en su forma tradicional.
La mayoría de las redes de señales gráficas son locales.
Así pues, las convoluciones se definen mediante estas sumas ponderadas.
de agregaciones locales.
Y esto también ocurre con la agregación.
redes de paso de mensajes.
Todos estos son solo nombres diferentes para el
Lo mismo.
Así que esto, supongo que podemos decirlo con seguridad.
Esto lo gestiona en particular nuestra comunidad aquí.
Pero cuando se trata del ámbito global y
A escala mesoscópica, existen algunos desafíos.
Por ejemplo, cuando se trata de encontrar
incrustaciones globales, por ejemplo, distancias de ruta más corta entre
dos nodos en un grafo, esto es difícil
para manejar arquitecturas locales como las GNN.
Tendrías que sentir la cantidad de
lúpulo igual al diámetro, que suele ser
No es algo que quieras.
En teoría, esto se puede manejar mediante un grafo.
transformadores, en particular densos, los llamados grafos densos
transformadores, que son aquellos que permiten cada nodo
atender a todos los demás nodos, incluso sin
una ventaja.
Sin embargo, sabemos que esto no es muy
eficiente porque esta atención densa se escala como O
de N al cuadrado.
Tienes que llenar este denso y por
matriz final.
Y en particular, al pensar en el más corto
problema de ruta, que es lo que vamos a ser
Hablando de ello en un segundo, si estuvieras
para almacenar todas las distancias más cortas desde un
nodo a todos los demás nodos en el
gráfico, que requiere incrustaciones n-dimensionales.
Y por lo tanto no puedes, por ejemplo, transferir esto
arquitectura a un gráfico más grande.
No tienes ninguna generalización sobre el tamaño.
Y además, quiero decir, podrías decir, está bien,
No quiero encontrar todas las distancias de los caminos más cortos.
Quiero encontrar la K superior, pero la
Los K no coincidirán entre los nodos.
Entonces tendrás este problema de los diferentes
Las dimensiones de incrustación corresponderán a diferentes nodos,
Y eso es muy malo para las GNN.
Esto perjudica enormemente la generalización.
Bien, entonces esta es un área donde ambos
Las GNN y los transformadores tienen dificultades.
Cuando se trata de incrustaciones mesoscópicas, la extracción de estas
Incrustaciones mesoscópicas, extrayendo esto mesoscópico, ¿verdad?
Entonces sabemos que, por ejemplo, si usted
tienen gráficos bien comportados, como gráficos densos,
Se pueden extraer cosas como comunidades mediante el uso de espectro
filtros, GNN espectrales, de los cuales los filtros convolucionales y
Las GNN son un tipo, ¿verdad?
Pero pueden ser difíciles de aprender y
práctica en algunos entornos.
Y por ejemplo, tengo, es un poco
un poco pequeño, pero la segunda referencia allí en
La diapositiva es un documento que escribimos.
hace unos años para ICASP, donde nosotros
demostraron que las GNN son un poco mejores
que las incrustaciones espectrales para encontrar comunidades en espacios dispersos
gráficos, porque esencialmente, en gráficos dispersos, como
Los K autovectores superiores no son tan informativos.
¿Como en los grafos densos, verdad?
Pero lo que hacen bien las GNN es interpolar.
el ruido proveniente de los otros vectores propios.
Sin embargo, el problema es que cuando quieres
transferir esa GNN a otros gráficos, incluso en
la misma clase de familia de grafos aleatorios, este
La interpolación de ruido no es muy transferible.
Y entonces tienes algunos desafíos, ¿verdad?
Aunque esto es factible, necesitas grandes cantidades.
campo receptivo suficiente, y hay algunos desafíos
asociado, por ejemplo, con grafos dispersos.
La idea aquí era intentar, en
Para tratar de abordar estos problemas, fue
tratar de preservar la métrica adecuada para
cada escala, ¿verdad?
Entonces, cuando hablas de escala global, yo tengo
He estado hablando mucho sobre las distancias entre nodos,
¿bien?
Y en particular, la distancia del camino más corto es
Una métrica válida, ¿verdad?
Entonces lo que haremos aquí es yo
te mostrará esta clase de algoritmos que
Creo que se ha estudiado durante un buen tiempo.
mientras que, y especialmente en estas comunidades de conferencias web
etcétera.
Y estos algoritmos, lo que hacen es...
Intenta, en un paso local, aprender algo
una especie de incrustación, y luego en un entorno global
paso, asegúrese de que cuando calcule distancias
Entre las incrustaciones, replican de alguna manera el camino más corto.
distancias.
Y veremos que estos son los peores.
caso por naturaleza, por lo que son un poco conservadores.
Y así, conmigo y mi colaborador, Shavik
Dara, lo que hicimos fue analizar estos
algoritmos en grafos aleatorios homogéneos, que es un
una clase de gráficos mucho más realista, para intentar
para obtener garantías de distorsión del caso promedio.
Así que esto es lo primero que vamos a hacer,
y luego también voy a mostrar algunos datos empíricos
resultados donde reemplazamos este paso local que
Lo aclararé más adelante.
momentos con una GNN.
Y esto nos permite tener cosas como
transferibilidad, todas las buenas propiedades de las GNN.
Esta será la primera parte, y
Luego, en la segunda parte, vamos a...
Ajustar la escala mesoscópica.
Entonces, aquí, lo que vamos a hacer es que...
voy a usar este tipo de incrustación llamado el
Incrustaciones de búsqueda de adyacencia máxima.
Estas ideas están inspiradas en las cascadas que se producen en la dinámica de la opinión pública.
Estos son esencialmente el trabajo de mi otro
Colaboradora, Meher, que es de esta zona.
Y lo que hacen estas incrustaciones es contar.
ocurrencias de nodos en saltos múltiples.
Para qué utilizaremos estas incrustaciones es:
para reconectar el gráfico de tal manera que estemos
capturando no solo estas conexiones locales en el
gráfico, pero también estas conexiones máximamente adyacentes.
Entonces hay nodos que podrían no ser
conectados por un borde, pero están en múltiples
una especie de rutas de múltiples saltos, y eso significa
Están conectados al máximo de alguna manera.
Y nuestro objetivo será reconfigurar el
gráfico, pase este gráfico a través de cualquier arquitectura como
una GNN o un transformador de grafos, y con suerte
a través de este recableado, podrá extraer más
de esta estructura mesoscópica.
Y aquí veremos que la métrica válida,
como la métrica apropiada es la resistencia efectiva,
y que podemos establecer un límite inferior para el
resistencia efectiva de estos bordes recableados que nosotros
lo añadiré.
Bien, comencemos con la primera parte.
Entonces, el problema que estamos tratando de resolver es...
La dirección aquí es para aproximar las distancias del camino más corto,
¿bien?
Esto es como un subproblema.
del problema del camino más corto.
Es un poco más sencillo.
No estás intentando encontrar el camino más corto.
Simplemente estás tratando de encontrar la distancia más corta.
Sabemos que hay un algoritmo que puedes
Se utiliza para encontrar problemas de caminos más cortos en particular,
pero el problema es que encontrar todo exacto
-distancias entre pares utilizando este algoritmo e incluso simplificaciones
Su coste es bastante prohibitivo a gran escala, ¿verdad?
Por lo tanto, su escala es O de N veces
N más M, donde N es el número
de nodos y M es el número de
aristas en el grafo.
Y así, una idea que se ha explorado
Mucho por parte de las personas que trabajan en este problema.
¿Es esta idea de incrustar nodos en algún
espacio tal que la distancia entre las incrustaciones
de los nodos en este espacio se aproximan a
distancia del gráfico, es decir, la distancia del camino más corto, ¿de acuerdo?
Y luego la calidad de estas incrustaciones es
medido por una distorsión multiplicativa, ¿verdad?
Entonces, si D es la aproximación,
queremos que sea inferior y superior
limitado de esta manera.
Decimos que esta aproximación tiene uno más
menos distorsión épsilon si está acotada inferiormente por
uno menos épsilon, la distancia real del camino más corto,
y limitado superiormente por uno más épsilon, el
¿Distancia real del camino más corto, de acuerdo?
Pasos, un paso local y un paso global.
El paso local se suele realizar sin conexión a internet.
Así que hacemos este paso para todos los
nodos por adelantado.
Y la forma en que funciona es que tomas una muestra,
Entonces te dan tu gráfico.
Aquí simplemente estoy omitiendo los bordes solo para
hacer que la imagen sea más nítida.
Pero lo que haces es tomar muestras de lugares emblemáticos.
conjuntos, conjuntos de puntos de referencia, S0 a SR. Y estos
son conjuntos de nodos semilla o nodos de referencia.
Así que aquí los represento con el color naranja.
nodos.
Y entonces lo que haces es empezar
la distancia de cada nodo en el grafo
al punto de referencia más cercano por conjunto, ¿verdad?
Así, cada nodo tendrá una dimensión r.
incrustación donde la j-ésima entrada de esa incrustación
es la distancia mínima entre usted y un
elemento de ese conjunto, ¿de acuerdo?
Esto se hace sin conexión para todos los nodos.
Normalmente la forma en que la gente hace esto es haciendo
Búsqueda en amplitud a partir de las semillas o puntos de referencia.
Y luego almacenas todas estas distancias.
Obtienes tus incrustaciones de nodos.
Puedes tener el paso global en un
¿Moda basada en consultas, verdad?
Así que puedo venir a mi servidor o
mi computadora y decir, quiero aproximar
El camino más corto entre U y V.
Entonces, la forma en que haces esto es...
mira estas incrustaciones y calcula algunas
una especie de aproximación de la distancia basada en
la desigualdad triangular.
Entonces hay dos tipos de formas clásicas
para hacer esto.
El primer método te da un límite inferior
para la distancia real del camino más corto, ¿verdad?
Entonces estoy escribiendo el límite inferior como el
subrayar.
Y luego aquí, quiero decir, el paso local
Es exactamente como lo describí, ¿verdad?
Estás creando esa incrustación por distancias desde cada
nodo a la semilla más cercana en cada uno
de los conjuntos.
Y luego en el paso global, y esto
Se llama algoritmo de Lugan, lo que haces es
utilizas la desigualdad triangular inversa y
obtener este límite inferior, pero esencialmente tomando el
Norma L infinito de la diferencia entre la
incrustaciones.
Entonces, lo que esto hace en la práctica es
está tratando de encontrar la distancia máxima entre
las incrustaciones en términos de coordenadas, ¿verdad?
Así que estás tratando de encontrar el conjunto
que alcanza esta distancia máxima.
Y luego está otro enfoque que se propuso.
en este algoritmo por, en este artículo, por
Dasarma y otros que te dan una ventaja
atado, ¿verdad?
Así que le da a esta D línea superior esa parte superior
delimita la distancia real del camino más corto.
Y aquí, nodos semilla, lo que también hacemos
es almacenamos el índice real del
semilla en SJ que logra esta distancia, ¿verdad?
Entonces queremos saber el tamaño, usted
saber, como el tamaño de la distancia de
el nodo de cada conjunto, que es el
nodo en ese sentido que está más cerca de
¿Tú, de acuerdo?
Entonces, ¿usando estos dos tipos de vectores, verdad?
Uno en nuestro vector dimensional y el otro
un escalar por nodo.
Cuando realizamos el paso global, utilizamos
la desigualdad triangular, no la inversa, sino la inversa
desigualdad triangular ahora para acotar superiormente el más corto
distancia del camino por el mínimo entre la suma
entre OXUJ y FXPJ de tal manera que las semillas
que alcancen la distancia mínima en la semilla
¿El partido de SJ está programado, verdad?
Esto es lo que tengo aquí, pero
para aproximar la distancia entre este U1 y
U2 aquí, necesito tener algo en común
semilla, ¿verdad?
Y por eso necesitas este extra
Incrustando aquí.
¿Qué ocurre?
Lo lamento.
Sí, dejaré de moverme.
Bueno.
Muy bien, estos dos son algoritmos clásicos.
Y como dije, estos algoritmos no significan
Cualquier cosa si no tienen garantías de distorsión, ¿verdad?
Por lo tanto, necesitamos una garantía de distorsión tanto para
El algoritmo de Bourgan y el algoritmo de Sarma.
El algoritmo de Bourgan nos da un límite inferior.
Y este teorema de aquí, que se basa en
El teorema de incrustación de Bourgan, la distorsión del límite inferior.
Este teorema en realidad, quiero decir, no necesariamente
aplicar solo al más corto de este mismo
importante artículo de Bourgan y luego más tarde por
Matuszek, donde esencialmente muestran la distorsión de
¿Incrustar espacios métricos en espacios de Hilbert, verdad?
Porque siempre pierdes algo cuando lo haces.
eso.
Y este es básicamente ese teorema aplicado a
este problema en particular.
Entonces, lo que dice el teorema es que, dado
un gráfico suficientemente grande, para cualquier constante C
que usted corrija, existen incrustaciones óptimas, que
¿Son estas incrustaciones de estrella X que tengo?
aquí, con dimensión al menos N a la
uno sobre C log N, de tal manera que el
El estimador del límite inferior tiene distorsión acotada, donde el
La distorsión viene dada por ese uno sobre dos
C menos uno.
¿Bueno?
Por ejemplo, si quisieras obtener
distorsión del orden, por ejemplo, veamos aquí.
Entonces, si hacemos 1.5, esto sería
ser la mitad, ¿verdad?
Entonces obtendrías algo como a
uno, como uno sobre 1,5 log N
incrustaciones que te dan una distorsión de una
La mitad está allí.
Bueno.
Luego, además de tener una garantía de distorsión para la
límite inferior, ¿verdad?
Así que para el algoritmo de Bourgan, también tenemos distorsión
garantías para el límite superior de ese más
artículo reciente.
Y en ese artículo, además de proponer este algoritmo,
También ofrecen garantías en cuanto se establecen las semillas.
Tengo la talla dos a la J, ¿de acuerdo?
Con J variando desde cero hasta el suelo
del logaritmo N.
Y la razón por la que necesitas esta construcción
una de las razones es porque, recuerda
que dije que siempre necesitas
tienen esta semilla común.
Siempre necesitas tener la semilla común.
Y por eso siempre necesitas tener en
Al menos un conjunto que tenga la talla uno, ¿verdad?
Porque es posible que no encuentres semillas coincidentes en
los demás.
Tienes que poner S a cero, te da
esa aproximación de desigualdad triangular.
Y lo que dice este teorema es que usted
¿Obtienes dos C menos una garantía de distorsión, verdad?
Para el límite superior, para su límite superior
aproximación de la ruta más corta con incrustaciones X estrella
con dimensión al menos N elevada a la una
sobre C log N.
Vale, entonces son muy similares.
Garantías de distorsión.
Y la misma dimensión mínima de incrustación.
Ahora bien, ¿cuál es el problema con estas distorsiones?
¿resultados?
El problema con ellos es que son
el peor caso en la naturaleza en el sentido de que
se mantienen incluso para, como imagina un gráfico
donde aproximar los caminos más cortos es muy difícil.
Por ejemplo, un gráfico donde podrías tener
como una especie de masa conectada agradable, pero
tienes como caminos muy largos, como
patas de araña o algo así, ¿verdad?
Aproximar los caminos más cortos en este grafo es muy
difícil si no pruebas una semilla en
ese camino.
Por lo tanto, estas garantías se mantienen incluso en ese caso.
Así que puedes imaginar que son bastante holgados,
¿bien?
Y ese es el peor de los casos.
Y además, porque estos tamaños de incrustación no son
Esto se vuelve prohibitivo a pequeña escala.
Y como dije, es pesimista para el
Gráficos estructurados que realmente tenemos, ¿verdad?
Y en realidad lo que hice a partir de los dos
Las diapositivas anteriores a esta son solo
expresó la dimensión de incrustación mínima en términos de
épsilon, porque ahora quiero tener uno menos
épsilon, uno más épsilon distorsión, es decir, distorsión limpia.
Y así ajusté el valor mínimo de incrustación.
tamaño.
Bien, entonces, ¿cuál es su gráfico de casos promedio?
¿bien?
¿Qué gráficos son más realistas?
¿Y más cercano a lo que tienes en la práctica?
Un modelo que se usa mucho para modelar
Este tipo de gráficos constituye el modelo de grafo aleatorio no homogéneo.
Y este modelo es básicamente una extensión de
un modelo de bloques estocásticos.
Entonces, lo que sucede es que en este modelo,
Cada nodo tiene un tipo, ¿verdad?
Entonces cada nodo pertenece a algo así como
un tipo o una familia, y el borde
La probabilidad dependerá del tipo de punto final.
Entonces tendrás una matriz D, que es
llamada matriz de afinidad que es una especie de
codificando la afinidad entre nodos de diferentes tipos.
Y lo que haces es para
calcular la probabilidad de que dos nodos se conecten en
este gráfico, divides la entrada correspondiente de
D por el número de nodos en el
una especie de comunidad de algo así como
¿Tu vecino, verdad?
Entonces D no es una probabilidad, sino cuando
tomas la proporción de eso con el
tamaño de la comunidad, tamaño de la comunidad de tu vecino, obtienes
una probabilidad.
Este modelo es muy general, por lo que incluye
cosas como el modelo de bloques estocásticos o el
Serenium cuando solo hay un tipo.
Y por eso nuestra idea es intentar
derivar esas garantías de distorsión ahora, no solo para
estos grafos aleatorios no homogéneos que son mejores
modelo de su gráfico típico que encuentra
en el mundo real.
Así que antes de hablar sobre nuestros resultados de distorsión,
Solo quiero darte una idea.
de la idea de la prueba.
Como dije antes, en estos algoritmos,
estos algoritmos locales globales, seguro que hay uno
aproximación de trayectoria, lo que haces es efectivamente,
Para calcular las incrustaciones, debes hacer lo siguiente:
Búsqueda en amplitud desde las semillas, ¿verdad?
Búsqueda en amplitud, puedes pensarlo
como exploración local, ¿verdad?
Entonces soy un nodo, miro mi
vecinos de un salto, luego mis vecinos de dos saltos,
etcétera.
Y como una especie de dinámica
proceso, puedes pensar en esto como un
proceso de ramificación, ¿verdad?
Y en particular, si tiene varios tipos,
Este será un proceso de ramificación de múltiples tipos.
con la matriz media dada por D, la afinidad
matriz.
Lo que puedes demostrar es que esta ramificación
proceso, que es básicamente, quiero decir, esto es
llamado a, es algo así como un binomio
proceso de ramificación, creo que se llama Galton
-Proceso Watson, y básicamente, es el proceso donde,
cada nodo cuando se ramifica, tiene
una serie de tipos de vecinos dados por
la media del proceso, que en este
En este caso, si tienes la matriz de afinidad D,
eso significa que va a ser lambda uno,
el valor propio formal de mostrar.
Utilizando esta aproximación del proceso de ramificación, se obtiene que el
límite del vecindario de k saltos del nodo
U es de orden lambda uno al
Vale, ¿verdad?
Y lo que mostramos a continuación, después de mostrar
estas concentraciones de ambos tamaños de límite de
el barrio k-hop y también el tamaño
de todo el barrio k-hop, es tu
capaz de demostrar que las distancias típicas se concentran utilizando
concentración de variables aleatorias de Bernoulli.
Esencialmente, DUV, donde DUV es la distancia típica,
se concentra alrededor de lambda base logarítmica uno de n,
¿bueno?
Y entonces esta distancia típica es lo que es
nos van a dar nuestra garantía de distorsión y
La concentración a su alrededor es lo que nos va a dar
Nuestra garantía de distorsión.
Este es nuestro resultado.
Así que usando esos dos algoritmos para el inferior
límite y límite superior, lo que mostramos
es que bajo condiciones de regularidad limitadas en el
modelo de grafo aleatorio no homogéneo, aquellos hitos o semillas
Las incrustaciones basadas en logran una distorsión de uno más menos épsilon.
con alta probabilidad con dimensión de incrustación, por lo que para
el límite inferior, al menos n al
uno menos épsilon log lambda uno n, y
entonces esta expresión más complicada para uno más
épsilon pero en la práctica, quiero decir, si tú
Olvídate de este mínimo aquí, obtienes algo
como, es como uno, creo que es uno
más épsilon o algo así.
Sí, gracias.
Sí, así es.
Entonces, mucho mejor, de acuerdo.
Así que hay algunas cosas interesantes que decir
¿Se fijan aquí, verdad?
Esto no se ve mucho mejor que el
incrustaciones que teníamos antes, pero son
Un poco mejor.
Entonces, lo primero que notas es
que esto ahora está gobernado por el espectro
radio, lambda uno de la matriz de afinidad y
este eta n aquí es el tipo mínimo
exponente de tamaño, ¿verdad?
Así que esto es una especie de control para no
tener tipos o comunidades muy desequilibradas, y qué
lo que ves es que los tipos más equilibrados...
te dan incrustaciones más pequeñas, y eso aunque
Esto todavía no se ve increíble, es polinómicamente más pequeño.
que esos peores casos, no garantías de distorsión, el
tamaños de incrustación en el peor de los casos aproximadamente de n a
épsilon sobre dos.
Entonces hay una especie de ganancia polinómica que
tienes aquí cuando te enfocas en lo homogéneo
o no gráficos, ¿verdad?
Como cuando te olvidas de los gráficos del peor escenario.
Ese fue nuestro principal resultado.
Otra cosa que puedes hacer es...
Esto se puede extender al caso de continuidad
tipos.
Entonces, en lugar de tener como un conjunto finito
de tipos como en un modelo de bloques estocásticos,
podrías tener infinitos tipos, por ejemplo,
como en un grafón, ¿verdad?
Y ahora tu D ya no es
una matriz, es un núcleo, y esto permite
usted para extender estos resultados a un nivel aún mayor.
un conjunto más amplio de gráficos más allá de SBM y Erdos
-Renyi, como los gráficos de Chung-Liu y otros,
y los límites de distorsión son muy similares.
La forma en que extiendes ese resultado de distorsión a
estos gráficos con infinitos tipos eres tú
una especie de sándwich en el núcleo, el núcleo continuo,
mediante núcleos de función escalonada y considere esos pasos
Los núcleos de las funciones deben ser grafos con tipos finitos.
Ese fue el tipo de contribución teórica a
derivar estas garantías de distorsión para más realistas, más
Gráficos del caso promedio.
En el aspecto numérico, lo que hicimos fue
reemplazamos el paso de búsqueda en amplitud en
el paso local de esos algoritmos con un
¿Un sustituto del camino más corto, verdad?
Así que se entrena simplemente mediante aprendizaje por imitación.
imitar la búsqueda en amplitud o el camino más corto desde
las semillas.
Aunque estas GNN no son adecuadas para
cálculo de la ruta más corta larga, para rutas más cortas cortas,
Lo hacen bastante bien.
Y lo que hicimos fue entrenar en
Gráficos pequeños, ¿verdad?
Entrenamos en un pequeño conjunto de 100 nodos y
grafo aleatorio homogéneo.
Este era un grafo aleatorio de Erdos-Renyi.
Y luego se transfirió a gráficos hasta 32
veces más grande.
Y lo que vemos aquí en esta diapositiva
es, entonces cuando tus gráficos son bastante dispersos,
¿bien?
Entonces cuando lambda es como tres y
cuatro, que está casi fuera del rango supercrítico
régimen para Erdos-Renyi, lo que ves es
Que la búsqueda en amplitud siempre gana.
Pero una vez que te vuelves un poco más denso,
entonces tu lambda está en cinco o seis,
Con el tiempo, se obtiene un mejor MSC con las GNN.
a un coste mucho menor, ¿verdad?
Así que como tienes que hacerlo, esto es para
las GNN, así que tienes que hacer paso
Menos cálculos, especialmente para gráficos de gran tamaño porque
La búsqueda en amplitud es exhaustiva, ¿verdad?
Las GNN solo llegan hasta k saltos,
capas l.
Luego también realizamos este experimento de verdad.
-redes mundiales, todavía utilizando nuestras GNN entrenadas en
esos gráficos sintéticos.
Y lo que hicimos aquí fue, de nuevo,
transferimos esas GNN a estos mundos reales.
gráficos con un orden de 10.000 nodos.
Y lo que vimos aquí fue que, sí,
como por ejemplo, partiendo de un cierto
tamaño del gráfico, obtienes un MSC más bajo cuando
usar GNN para aproximar la amplitud del límite inferior
-primera búsqueda.
Y nuestro principal objetivo aquí era simplemente
ver, ¿cómo se comportan estos gráficos aleatorios no homogéneos?
¿Practicar como un gráfico promedio del mundo real?
Y dados estos resultados, sentimos que ellos
deben comportarse lo suficientemente como estos IHG para el
teoría para sostener.
Bien, este es el final de la parte
uno.
Supongo que ahora puedo responder preguntas si
¿Hay alguna pregunta antes de que continúe?
a la segunda parte.
Entonces, la pregunta que vi aquí fue cómo
para seleccionar los conjuntos de semillas.
Así que en la práctica, simplemente los pruebas en
Es algo aleatorio, pero es un problema importante, ¿verdad?
Y puedes encontrar formas más inteligentes de hacerlo.
él.
Por ejemplo, creo que la mejor manera
para hacerlo es tomar muestras de semillas con
Alta centralidad, ¿verdad?
Porque no van a ser solo muy locales
Conectado, pero muy central en el gráfico.
De acuerdo, entonces seguiré adelante.
Entonces, en la segunda parte, como mencioné
antes, lo que vamos a hacer es que estamos
voy a intentar recablear los gráficos de tal manera
en cuanto a preservar o explotar la estructura mesoscópica
un poco mejor en el procesamiento de señales y
pipelines de aprendizaje automático.
Y la razón de ello es porque ambos
Las GNN y los transformadores de grafos pueden tener dificultades en esto.
Escala mesoscópica, ¿verdad?
Entonces, redes neuronales gráficas o paso de mensajes convolucionales
GNN, se agregan sobre vecindarios de k saltos donde
Normalmente quiero que k sea pequeño.
Por lo tanto, este campo receptivo es local.
Y como mencioné anteriormente, en algunas situaciones,
Es posible que tengas dificultades para acceder a las comunidades.
y cuellos de botella y ese tipo de cosas.
A veces la gente lo llama alisado excesivo, aplastamiento excesivo,
¿bien?
Y luego, cuando se trata de transformadores de gráficos
con atención intensa, tienen, en cierto modo,
Quiero decir, si no vas a usar el
estructura del gráfico, derecha, para calcular sus pares de atención,
De alguna manera pierdes ese gráfico anterior.
Es lo que hace que las GNN funcionen tan bien.
Y además, tienes esta O de N
atención cuadrada que es muy prohibitiva para grandes
gráficos.
Al mismo tiempo, ya estoy motivado, ¿verdad?
Pero como nosotros,
Y luego, cuando se trata de transformadores de gráficos
con atención intensa, tienen algo así como,
Quiero decir, si no vas a usar el
estructura del gráfico, derecha, para calcular sus pares de atención,
De alguna manera pierdes ese gráfico anterior.
hace que las GNN funcionen tan bien y además usted
tener esta atención O de N al cuadrado que
resulta muy prohibitivo para gráficos grandes.
Al mismo tiempo, y esto ya lo he dicho
motivados, correcto, pero como queremos en
algunos problemas, en algunos problemas las representaciones que
queremos aprender o diseñar, ellos, nosotros
quieren que reflejen cosas como las comunidades y
cuellos de botella.
Una cosa que hace eso son los saltos múltiples
paseos, ¿verdad?
Entonces, si tomas varios, digamos, paseos aleatorios
de longitud suficientemente grande y uno tiene algo así como
estadísticas promedio que usted recopila en estas caminatas,
En gráficos bien comportados, puedes
obtener, cada uno recablea el gráfico promoviendo estos
pares que aparecen repetidamente en el
mismos paseos con múltiples saltos.
Para ello, vamos a utilizar
esta idea de dinámica de contagio desde la opinión
dinámica y vamos a usar dos qué
llaman reglas de cascada para descubrir este mesoscópico
estructura, búsqueda de adyacencia máxima y búsqueda de adyacencia por umbral.
Entonces, la forma en que funcionan es que empiezan
con una semilla aleatoria.
Además de activar esta semilla aleatoria en el paso cero,
También activas un conjunto aleatorio de nodos.
y luego en cada paso lo que vas a hacer
lo que tienes que hacer es activar el
nodo inactivo con los vecinos más activos en
Búsqueda de adyacencia máxima.
Vas a ser un poco más indulgente.
con esta activación y vas a activar
cualquier nodo inactivo que tenga al menos kappa
vecinos activos.
Estas reglas son solo dos reglas diferentes para
Haz lo mismo, ¿verdad?
Como si ambos fueran privilegiados, estos pares de saltos múltiples
que están respaldadas por rutas cortas redundantes, que
es esta estructura mesoscópica que estamos tratando de
para extraer.
Y aquí solo tengo dos videos.
mostrando cascada de umbral con dos parámetros kappa.
Así que aquí, es un poco rápido, pero tú
Como puedes ver, lo inicializo a cero.
También tomo muestras de los nodos cuatro y tres y
Entonces empiezo a mirar estos elementos lo más adyacentes posible.
nodos adyacentes a cero, cuatro y tres y
Hago esto repetidamente durante un cierto número
de pasos.
Esto es para umbrales pequeños que terminan
activando muchos nodos al final.
Así que terminan activando 10 de cada
60 nodos.
Aquí, si aumentas un poco el umbral
un poco, las activaciones son más raras.
Naturalmente, estás activando, eventualmente estás activando el uno
-vecinos saltando.
Así que no te vas a deshacer de este local
estructura, pero hay cierta selectividad en cómo lo haces
¿Activando a tus vecinos de salto más lejanos, verdad?
Tus vecinos de dos saltos, tres saltos y así sucesivamente
en.
Por lo tanto, esta selectividad se basa en este máximo.
idea de adyacencia.
Y también estos gráficos auxiliares, no son tan...
No es muy caro de construir, ¿verdad?
Como si, si m es de orden n,
Esto va a ser O de n
construir.
Y entonces la idea es tomar estos
gráficos auxiliares y los pasa como la columna vertebral
a una GNN o a un transformador de gráficos.
Así que tenemos un par de resultados teóricos.
para respaldar de alguna manera este enfoque.
Una de ellas demuestra que la reconfiguración ayuda cuando...
tienen gráficos que son heterofílicos.
Entonces, aquí, supongamos que tenemos que
¿Puedo escribir tres eventos, verdad?
Entonces, el primero son los acuerdos de etiquetas, lo que significa
Los nodos tienen la misma etiqueta en cualquier tarea.
estás tratando de resolver.
Esta será una L caligráfica, evento L caligráfico.
El evento caligráfico E será que hay un
borde, no un borde dirigido, solo un borde
entre los nodos U y V, lo que significa que son adyacentes
en el gráfico.
Y la R caligráfica significará que tienes
refuerzo, lo que significa que hay al menos kappa co
-ocurrencias de U y V en.
Entonces, dados estos eventos y dado un aleatorio
par no ordenado de nodos distintos U, V, nosotros
define la homofilia de arista estándar como la probabilidad
que usted tiene un acuerdo de etiqueta dado que usted
tienen una ventaja entre U y V, y
la homofilia de refuerzo o la homofilia en la
gráfico reconectado como la probabilidad de que tengas
acuerdo de etiqueta dado que tiene refuerzo, o
en otras palabras, dado que tienes adyacencia
en el gráfico reconectado.
Y entonces lo que estábamos preguntando aquí era,
¿Cuándo se presenta esta homofilia en el gráfico reconfigurado?
¿Mayor que la homofilia en el gráfico original?
La razón de esto es porque sabemos
que las convoluciones gráficas de GNN funcionan bien cuando
¿Tienen homofilia, verdad?
Entonces, cuando nodos similares, nodos no similares, nodos
que están conectados en el gráfico tienen similares
vecinos, etiquetas similares o, por ejemplo, señales.
Esto es lo que mide la energía de Dirichlet, ¿verdad?
Más en nuestra conversación, más en procesamiento de señales
términos.
Entonces, lo que mostramos en esta proposición aquí
es que bajo dos condiciones.
Entonces, bajo la condición de que tengamos un orden
de heterofilia en G, lo que significa que siempre que la
Las etiquetas entre dos nodos U y V coinciden,
tienes una mayor probabilidad de que sean
en la ruta de múltiples saltos en comparación con que sean
vecinos directos.
Y cuando el evento de refuerzo es menos frecuente
que los bordes, entonces la homofilia de ese cableado reconectado
El gráfico es mayor que la homofilia de la
gráfico original.
Y esto es mayor o igual que, pero
Será estricto cuando se den estas condiciones.
estricto.
Y aquí intentamos ilustrar esto con
Algunos gráficos sintéticos y reales.
Entonces lo que hicimos fue que nosotros, la homofilia
antes y después del recableado, en comparación con el registro de
el grado promedio original y los tamaños de
Las bolas aquí indican la homofilia.
Los puntos tan pequeños, como estos, tienen una baja homofilia.
Los círculos más grandes presentan una alta homofilia.
Y entonces lo que ves es que nosotros
obtener el mayor aumento de homofilia justo aquí
aquí cuando los gráficos originales son heterofílicos y
cuando tienen un título universitario alto, ¿verdad?
En algunos casos, la homofilia empeora, como
especialmente para grafos de bajo grado muy homofílicos.
Bien, y luego los otros resultados que tenemos
lo tenemos, y este es un resultado muy simple,
Está muy relacionado con lo que Antonio comentó sobre
Lunes, la resistencia efectiva de los bordes en
¿El gráfico reconectado, verdad?
Entonces, básicamente, quiero decir, lo que estamos capturando una vez
Realizamos esta reconfiguración neuronal basándonos en la coactivación.
correcto, o nodos que aparecen en múltiples saltos múltiples
rutas, es que estamos codificando redundancia estructural, ¿verdad?, en
el gráfico.
Y básicamente lo que esa redundancia estructural significa formalmente.
Si es eso, entonces lo que eso significa es que
G tiene K caminos cortos disjuntos por pares de aristas.
desde la semilla hasta ti, ¿verdad?
Y esto limita directamente la resistencia efectiva I
probablemente no sea necesario volver a definir esto después
La charla de Antonio, pero básicamente se trata solo de medir el tipo
como la diferencia de voltaje entre dos nodos,
correcto, basado en la pseudoinversa de la
Laplaciano aquí, si crees que tienes
una fuente actual en U y una actual
fregadero en V.
Y el límite superior que obtenemos para
esta resistencia efectiva en estos bordes recableados es
dada por L, que es la longitud de
el kappa, donde kappa es el umbral de activación.
Bien, entonces esencialmente aquí, no es que estemos
no estamos preservando los cuellos de botella, ¿verdad?, porque los cuellos de botella son
nodos con, son bordes con alta resistencia efectiva.
Estamos preservando estos redundantes, por lo que estos pares que
corresponder a redundante, a redundancia en el gráfico.
Estamos preservando, estamos conectando nodos con baja efectividad
resistencia.
Bien, entonces solo unos pocos resultados numéricos antes
Concluyo.
Entonces, y lo que vimos fue, primero de
En general, funciona bastante bien.
Entonces, en algunos conjuntos de datos, logra,
como, la mejor actuación.
En otros casos, lo hace comparativamente con el uso del
gráfico original, que es, que es bonito.
Pero tal vez lo más interesante sea el
alineación con la teoría.
Así que vemos que las mayores ganancias
ocurren para gráficos heterofílicos con un alto grado.
Cuando los supuestos de ese primer teorema sobre
la, sobre la homofilia mejorada de la, de
Si el gráfico reconfigurado no se sostiene, entonces no lo hicimos.
Se observan muchas ganancias.
Así que esto parece ser más útil.
para gráficos heterofílicos.
Aunque agnósticos, esto es solo GCN, ¿verdad?
y estas son tres arquitecturas diferentes de transformadores de gráficos.
Todos estos son una especie de grafo disperso.
transformadores donde no tienes la estructura del gráfico,
pero de alguna manera les das a los vecinos incrustaciones
como fichas.
Así que puedes usar este gráfico reconfigurado.
allá.
En estos dos casos, hemos tenido una mejora bastante notable.
Y aquí, hay más detalles sobre
la mejora que obtuvimos en estos heterofílicos
conjuntos de datos, ¿verdad?
Así que, especialmente para Chameleon y Cornell, las mejoras
eran, eran bastante buenos.
Otra de las mejores precisiones que obtuvimos en estos
gráficos reconectados, en la etiqueta homofilia, el logaritmo
grado promedio y la conectividad de la, de
tanto el gráfico original como el recableado.
Y lo que vimos es que, entonces M
-ASTAS aquí están nuestros
métodos, ¿verdad?
Entonces los valores de beta aquí, pero
especialmente centrándonos en el R cuadrado, el ajustado
R cuadrado aquí, ya que, como puede ver, el
diferencia en, en, o la precisión de la prueba, la
Las mejoras en la precisión de las pruebas se explican mucho mejor.
por las propiedades estructurales de este grafo reconfigurado
En el gráfico original, ¿verdad?
Entonces hay mejoras en la homofilia y esto
cambio en la resistencia efectiva en el gráfico recableado
Parece que sí ayudan al rendimiento.
Bueno, para concluir, hoy hablé
sobre el intento de preservar la topología mesoscópica y global
en, en gráficos.
Para aproximar las distancias globales, vimos ese hito.
Las incrustaciones son un buen método, ¿verdad?
Eso todavía tiene ese paso local,
pero luego lo aumenta con un, con un
paso global.
Y aunque la distorsión garantiza que estos
Los algoritmos son bastante malos en el peor de los casos,
vemos que en los gráficos de casos más promedio,
La distorsión es.
También vimos que existe una dependencia interesante.
sobre la dimensión de incrustación en el Peronico, y
que podemos reemplazar esa búsqueda en amplitud
entrar, en el paso local con un
GNN sustituto que luego nos permite ordenar
de aprovechar las buenas propiedades de GNN tales
como, como transferibilidad.
Y luego en la segunda parte, hablando de
Para incrustar o preservar la estructura mesoscópica, utilizamos gráficos.
cascadas.
En estas escalas mesoscópicas globales, convoluciones y atención
puede ser insuficiente, ¿verdad?
Entonces, una posible, quiero decir, hay muchas
enfoques a estas estructuras, correcto, para obtener incrustaciones
que incorporan estas estructuras.
Pero el enfoque que adoptamos aquí, y
el enfoque que yo, yo, yo creo que es,
ya sabes, sostengo que es un buen enfoque,
es hacer uso del apropiado
métrica, correcto, para intentar preservar lo apropiado
métrico.
Así pues, a escala global, el camino más corto
métrica, en la escala local, en la escala mesoscópica,
cosas como resistencia efectiva, redundancia y aquí estamos
Intenta hacerlo de dos maneras.
Entonces, primero, dentro del modelo ML, ¿verdad?, entonces
tratando de aprender incrustaciones que, y en el
Al tratar de preservar la escala mesoscópica, lo hicimos
por lo tanto fuera del modelo ML a través de la reconfiguración,
Correcto, y las infraestructuras troncales de ML y SP existentes.
Ahora, en cuanto a la dirección futura, en relación con lo que
Sergio preguntó, una cosa que podemos hacer
¿Podemos hacer una mejor semilla o hito?
selección, ¿verdad?
Por lo general, esto se hace de forma uniforme y aleatoria.
Nuestros resultados dependen de ello, pero en la práctica usted
podría hacerlo mejor usando el grado o la centralidad,
incluso utilice la estructura en cascada en estos aleatorios
paseos para seleccionar los lugares de interés.
Otra dirección que estamos siguiendo es la de extender esas
garantías de distorsión de incrustación de ruta más corta para grafos dirigidos,
lo cual es un poco más desafiante porque
Ahora su matriz D no es simétrica y
tienes que asegurarte de que estás respetando el
orientaciones de los bordes individuales.
También podría hacerse alguna señal o función sensible
Selección en cascada, ¿verdad?
Así que ignoramos por completo las características del nodo cuando
estamos haciendo la selección en cascada o cuando
estamos calculando esos nodos adyacentes máximos
pares.
Y finalmente, porque realmente nos estamos centrando en
este método de recableado en nodos que tienen algunos
redundancia estructural a escala mesoscópica, el método
termina por no funcionar bien para gráficos donde
tienes cuellos de botella o problemas donde el
Los cuellos de botella son importantes.
Así que tal vez combinar este método de recableado con algunos
La reestructuración dirigida a los cuellos de botella podría darnos mejores resultados.
a escala mesoscópica y nos permite
cruzar cortes más estrechos.
Gracias, entonces estos son los dos documentos.
y gracias a mis colaboradores.
Gracias.
Johanna, gracias por la presentación.
Disculpen si me lo perdí.
Tengo curiosidad por los resultados, dado que
Se dice que los transformadores de gráficos son naturalmente mejores para los heterofílicos.
tareas, ya sea que esta mejora independiente del modelo ponga
Las GNN están a la par para observar una diferencia.
Sí, no creo que tenga la materia prima.
En términos numéricos, pero en la práctica los transformadores estaban funcionando mejor.
Sí, casi siempre.
Además, creo que solo probamos GCN.
GCN no es muy bueno para esto.
Sí, eso también podría ser un artefacto.
Veo.
Gracias.
Yo también tengo una pregunta sobre la primera parte.
Por lo general, estas redes reales siempre tienen una carencia.
bordes.
Afectan a la búsqueda de la ruta más corta, etc.
Lo que la gente a veces hace, todavía los incorporan.
en un espacio hiperbólico o cualquier otro espacio
y tratar de averiguar allí cómo
encontrar los caminos más cortos.
¿Crees que ahora es posible extenderlo?
¿él?
Respuesta a ¿existe un camino más corto entre?
dos nodos desconectados no, no los hay.
O como el camino más corto tiene, el más corto
La distancia es infinita.
Bien, entonces asumimos o porque, entonces
cuando hacemos esta aproximación del proceso de ramificación,
supongamos que estamos en el régimen supercrítico y
Allí, con alta probabilidad, tienes uno gigante.
componente conectado.
Así que aprovechamos eso, ¿verdad?
Es importante, sí.
Hablaste de recablear allí como una manera
para mitigar esto e investigar.
La gente también analiza en detalle los nodos virtuales.
Lo cual sería en lugar de simplemente recablear en
de los nodos existentes, tienes un nodo adicional
y luego puedes hacer ambos recableados o
nuevos bordes con eso.
Y tengo la sensación de que lo hará.
Realmente ayudan en algunos de estos aspectos.
Sí, entonces, si no me equivoco, esto
VCR uno, creo que la V significa
virtual.
Entonces creo que es uno de los gráficos
transformadores que tienen esta ventaja virtual.
Entonces quiero decir que mantenemos la ventaja virtual,
pero solo añadimos este recableado, ¿verdad?
Y aún se aprecian algunas mejoras importantes.
Así que supongo que sí, ayuda.
Porque el nodo virtual, si lo piensas
es como agregar este global
Es como un nodo que conecta a todo el mundo, ¿verdad?
Eso es cierto, eso es cierto, sí.